#ifndef SOLUTION_H_
#define SOLUTION_H_
#include <string>
#include <vector>
using namespace std;

class Solution 
{
public:
    string getPermutation(int n, int k) 
	{
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
		typedef unsigned int uint;
		vector<int> num(n);
		vector<bool> phs(n,false);
		vector<uint> factorials(n);
		factorials[0] = factorials[1] = 1;
		for(int i=2;i<n;i++)
			factorials[i] = i*factorials[i-1];

		for(int i=0;i<n;i++)
		{
			int idx = k/factorials[n-i-1];
			idx += (k%factorials[n-i-1])>0;

			int j=0;
			for(int m=0;m<idx;j++)
			{
				if(!phs[j])
					m++;
			}
			num[i] = j;
			phs[j-1] = true;
			k-=(idx-1)*factorials[n-i-1];
		}
		


		string ss(n,'0');
		for(size_t i=0;i<num.size();i++)
			ss[i] += num[i];

		return ss;        
    }
};
#endif